Complexity of Manipulating Sequential Allocation
Identifieur interne : 000026 ( France/Analysis ); précédent : 000025; suivant : 000027Complexity of Manipulating Sequential Allocation
Auteurs : Haris Aziz [Australie] ; Sylvain Bouveret [France] ; Jérôme Lang [France] ; Simon Mackenzie [États-Unis]Source :
Descripteurs français
Abstract
Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.
Url:
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000719
- to stream Hal, to step Curation: 000719
- to stream Hal, to step Checkpoint: 000031
- to stream Main, to step Merge: 000031
- to stream Main, to step Curation: 000031
- to stream Main, to step Exploration: 000031
- to stream France, to step Extraction: 000026
Links to Exploration step
Hal:hal-01501842Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr">Complexity of Manipulating Sequential Allocation</title>
<author><name sortKey="Aziz, Haris" sort="Aziz, Haris" uniqKey="Aziz H" first="Haris" last="Aziz">Haris Aziz</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-134757" status="INCOMING"> <orgName>University of South Wales</orgName>
<desc> <address> <country key="AU"></country>
</address>
</desc>
<listRelation> <relation active="#struct-332681" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-332681" type="direct"><org type="institution" xml:id="struct-332681" status="INCOMING"> <orgName>University of South Wales</orgName>
<desc> <address> <country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Australie</country>
</affiliation>
</author>
<author><name sortKey="Bouveret, Sylvain" sort="Bouveret, Sylvain" uniqKey="Bouveret S" first="Sylvain" last="Bouveret">Sylvain Bouveret</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-5032" status="INCOMING"> <orgName>Institut national Polytechnique de Grenoble</orgName>
<orgName type="acronym">INP GRENOBLE</orgName>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.inpg.fr/</ref>
</desc>
<listRelation> <relation active="#struct-300275" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300275" type="direct"><org type="institution" xml:id="struct-300275" status="OLD"> <idno type="IdRef">026388804</idno>
<orgName>Institut National Polytechnique de Grenoble </orgName>
<orgName type="acronym">INPG</orgName>
<date type="end">2006-12-31</date>
<desc> <address> <addrLine>46 avenue Félix Viallet 38031 Grenoble Cedex 1</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Lang, Jerome" sort="Lang, Jerome" uniqKey="Lang J" first="Jérôme" last="Lang">Jérôme Lang</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-989" status="VALID"><orgName>Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision</orgName>
<orgName type="acronym">LAMSADE</orgName>
<desc><address><addrLine>Place de Lattre de Tassigny 75775 PARIS CEDEX 16</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lamsade.dauphine.fr/</ref>
</desc>
<listRelation><relation active="#struct-300302" type="direct"></relation>
<relation name="UMR7024" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300302" type="direct"><org type="institution" xml:id="struct-300302" status="VALID"><orgName>Université Paris-Dauphine</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR7024" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Mackenzie, Simon" sort="Mackenzie, Simon" uniqKey="Mackenzie S" first="Simon" last="Mackenzie">Simon Mackenzie</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID"> <orgName>Computer Science Department - Carnegie Mellon University</orgName>
<desc> <address> <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cs.cmu.edu/</ref>
</desc>
<listRelation> <relation active="#struct-378064" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING"> <orgName>University of Pittsburgh</orgName>
<desc> <address> <country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01501842</idno>
<idno type="halId">hal-01501842</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-01501842</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-01501842</idno>
<date when="2017-02">2017-02</date>
<idno type="wicri:Area/Hal/Corpus">000719</idno>
<idno type="wicri:Area/Hal/Curation">000719</idno>
<idno type="wicri:Area/Hal/Checkpoint">000031</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000031</idno>
<idno type="wicri:Area/Main/Merge">000031</idno>
<idno type="wicri:Area/Main/Curation">000031</idno>
<idno type="wicri:Area/Main/Exploration">000031</idno>
<idno type="wicri:Area/France/Extraction">000026</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="fr">Complexity of Manipulating Sequential Allocation</title>
<author><name sortKey="Aziz, Haris" sort="Aziz, Haris" uniqKey="Aziz H" first="Haris" last="Aziz">Haris Aziz</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-134757" status="INCOMING"> <orgName>University of South Wales</orgName>
<desc> <address> <country key="AU"></country>
</address>
</desc>
<listRelation> <relation active="#struct-332681" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-332681" type="direct"><org type="institution" xml:id="struct-332681" status="INCOMING"> <orgName>University of South Wales</orgName>
<desc> <address> <country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Australie</country>
</affiliation>
</author>
<author><name sortKey="Bouveret, Sylvain" sort="Bouveret, Sylvain" uniqKey="Bouveret S" first="Sylvain" last="Bouveret">Sylvain Bouveret</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-5032" status="INCOMING"> <orgName>Institut national Polytechnique de Grenoble</orgName>
<orgName type="acronym">INP GRENOBLE</orgName>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.inpg.fr/</ref>
</desc>
<listRelation> <relation active="#struct-300275" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300275" type="direct"><org type="institution" xml:id="struct-300275" status="OLD"> <idno type="IdRef">026388804</idno>
<orgName>Institut National Polytechnique de Grenoble </orgName>
<orgName type="acronym">INPG</orgName>
<date type="end">2006-12-31</date>
<desc> <address> <addrLine>46 avenue Félix Viallet 38031 Grenoble Cedex 1</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Lang, Jerome" sort="Lang, Jerome" uniqKey="Lang J" first="Jérôme" last="Lang">Jérôme Lang</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-989" status="VALID"><orgName>Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision</orgName>
<orgName type="acronym">LAMSADE</orgName>
<desc><address><addrLine>Place de Lattre de Tassigny 75775 PARIS CEDEX 16</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lamsade.dauphine.fr/</ref>
</desc>
<listRelation><relation active="#struct-300302" type="direct"></relation>
<relation name="UMR7024" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300302" type="direct"><org type="institution" xml:id="struct-300302" status="VALID"><orgName>Université Paris-Dauphine</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR7024" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"> <idno type="IdRef">02636817X</idno>
<idno type="ISNI">0000000122597504</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc> <address> <country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Mackenzie, Simon" sort="Mackenzie, Simon" uniqKey="Mackenzie S" first="Simon" last="Mackenzie">Simon Mackenzie</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID"> <orgName>Computer Science Department - Carnegie Mellon University</orgName>
<desc> <address> <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
<country key="US"></country>
</address>
<ref type="url">http://www.cs.cmu.edu/</ref>
</desc>
<listRelation> <relation active="#struct-378064" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING"> <orgName>University of Pittsburgh</orgName>
<desc> <address> <country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>game theory</term>
<term>manipulation</term>
<term>resource allocation</term>
<term>sequential allocation</term>
<term>social choice</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
<li>États-Unis</li>
</country>
<region><li>Pennsylvanie</li>
</region>
<settlement><li>Pittsburgh</li>
</settlement>
<orgName><li>Université de Pittsburgh</li>
</orgName>
</list>
<tree><country name="Australie"><noRegion><name sortKey="Aziz, Haris" sort="Aziz, Haris" uniqKey="Aziz H" first="Haris" last="Aziz">Haris Aziz</name>
</noRegion>
</country>
<country name="France"><noRegion><name sortKey="Bouveret, Sylvain" sort="Bouveret, Sylvain" uniqKey="Bouveret S" first="Sylvain" last="Bouveret">Sylvain Bouveret</name>
</noRegion>
<name sortKey="Lang, Jerome" sort="Lang, Jerome" uniqKey="Lang J" first="Jérôme" last="Lang">Jérôme Lang</name>
</country>
<country name="États-Unis"><region name="Pennsylvanie"><name sortKey="Mackenzie, Simon" sort="Mackenzie, Simon" uniqKey="Mackenzie S" first="Simon" last="Mackenzie">Simon Mackenzie</name>
</region>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000026 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000026 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Amérique |area= PittsburghV1 |flux= France |étape= Analysis |type= RBID |clé= Hal:hal-01501842 |texte= Complexity of Manipulating Sequential Allocation }}
This area was generated with Dilib version V0.6.38. |